package leetcode;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class LeetCode739 {

    public static void main(String[] args) {
        LeetCode739 leetCode739 = new LeetCode739();
        System.out.println(Arrays.toString(leetCode739.dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72, 76, 73})));
    }

    //当前元素小于栈顶元素 入栈
    //当前元素大于栈顶元素 则出栈所有比这个元素小的元素 最后将这个数据入栈
    public int[] dailyTemperatures(int[] T) {
        int[] result = new int[T.length];
        //记录数组下标
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < T.length; i++) {
            if (stack.isEmpty() || T[i] < T[stack.peek()]) {
                stack.push(i);
                continue;
            }
            while (!stack.isEmpty() && T[i] > T[stack.peek()]) {
                Integer pop = stack.pop();
                result[pop] = i - pop;
            }
            stack.push(i);
        }
        return result;
    }
//------------------------------------------------------------------
}
